package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
/**
 * Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
 * @author Adiy
 *
 */
public class SubSetsII {

	public static void main(String[] args) {

		int[] nums={4,4,4,1,2,4};
		List<List<Integer>> subsetList=subsets(nums);
		Iterator<List<Integer>> it=subsetList.iterator();
		while(it.hasNext()){
			System.out.println(it.next());
		}
		
	}

	 public static List<List<Integer>> subsets(int[] nums) {
	        
	    	
	    	
	    	
	    	List<List<Integer>> subsetList=new ArrayList<List<Integer>>();
	        List<Integer> emptySubset=new ArrayList<Integer>();
	        List<Integer> fullSubset=new ArrayList<Integer>();
	        for(int i=0;i<nums.length;i++){
	        	fullSubset.add(nums[i]);
	        }
//	        subsetList.add(emptySubset);
//	          subsetList.add(fullSubset);
//	        
//	        for(int i=0;i<nums.length;i++){
//	        	List<Integer> subset=new ArrayList<Integer>();
//	        	subset.add(nums[i]);
//	        	subsetList.add(subset);
//	        }
//	     
//	        int len=fullSubset.size();
//	        List<Integer> copyFull=new ArrayList<Integer>();
//	        for(int i=0;i<nums.length;i++){
//	        	copyFull.add(nums[i]);
//	        }
//	        while(len>1){
//	        	for(int k=0;k<copyFull.size();k++){
//	            Integer obj=copyFull.remove(k);
//	            System.out.println("===="+copyFull);
//	        	if(!subsetList.contains(copyFull)){
//	        		subsetList.add(copyFull); 
//	        	}  
//	        	copyFull.add(k, obj);;
//	        	}
//	        	len--;
//	        }
	        Collections.sort(fullSubset);
	        getSubset(fullSubset, nums.length, subsetList);
	        subsetList.add(fullSubset);
	        return subsetList;
	    }
	    
	    public static void getSubset(List<Integer> list,int len,List<List<Integer>> subsetList){
	    	 if(list==null){
	    		 subsetList=new ArrayList<List<Integer>>();
	    		 return;
	    	 }
	    	 
			for (int k = 0; k <list.size(); k++) {
				Integer obj = list.remove(k);
				List<Integer> newList=new ArrayList<Integer>();
				newList.addAll(list);
				Collections.sort(newList);
				if (!subsetList.contains(newList)){
					subsetList.add(newList);
					List<Integer> nList=new ArrayList<Integer>();
					nList.addAll(newList);
					getSubset(nList, len-1, subsetList);
				}

				list.add(k, obj);
		
				
				
			}
	    	
	    	
	    }

}
